import random


class Node:
    def __init__(self, key, color='RED'):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
        self.color = color


class RedBlackTree:
    def __init__(self):
        self.nil = Node(0, color='BLACK')  # 叶节点
        self.root = self.nil

    def insert(self, key):
        # 创建节点
        new_node = Node(key)
        new_node.left = self.nil
        new_node.right = self.nil

        parent = None
        current = self.root
        while current != self.nil:
            parent = current
            if new_node.key < current.key:
                current = current.left
            else:
                current = current.right

        new_node.parent = parent
        if parent is None:
            self.root = new_node
            self.root.color = 'BLACK'
        elif new_node.key < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node

        self._fix_insert(new_node)

    def _fix_insert(self, node):
        while node != self.root and node.parent.color == 'RED':
            # RB
            if node.parent == node.parent.parent.left:
                uncle = node.parent.parent.right
                # RBR
                if uncle.color == 'RED':
                    node.parent.color = 'BLACK'
                    uncle.color = 'BLACK'
                    node.parent.parent.color = 'RED'
                    # 转化为插入的是爷爷节点
                    node = node.parent.parent
                # RB
                else:
                    if node == node.parent.right:
                        node = node.parent
                        self._left_rotate(node)
                    # 统一转化为R_RB
                    node.parent.color = 'BLACK'
                    node.parent.parent.color = 'RED'
                    self._right_rotate(node.parent.parent)
            else:
                uncle = node.parent.parent.left
                if uncle.color == 'RED':
                    node.parent.color = 'BLACK'
                    uncle.color = 'BLACK'
                    node.parent.parent.color = 'RED'
                    node = node.parent.parent
                else:
                    if node == node.parent.left:
                        node = node.parent
                        self._right_rotate(node)
                    node.parent.color = 'BLACK'
                    node.parent.parent.color = 'RED'
                    self._left_rotate(node.parent.parent)

        self.root.color = 'BLACK'

    def delete(self, key):
        node = self._find_node(key)
        if node == self.nil:
            print('node cannot find')
            return
        delete_node = node
        if delete_node.left == self.nil:
            x = delete_node.right
        elif delete_node.right == self.nil:
            x = delete_node.left
        else:
            # 后继节点
            y = self._successor(delete_node)
            delete_node.key = y.key
            delete_node = y
            x = delete_node.right

        self._transplant_p(delete_node, x)


        if delete_node.color == 'BLACK':
            self._fix_delete(x)

    def _fix_delete(self, node):
        while node != self.root and node.color == 'BLACK':
            if node == node.parent.left:
                sibling = node.parent.right
                if sibling.color == 'RED':
                    sibling.color = 'BLACK'
                    node.parent.color = 'RED'
                    self._left_rotate(node.parent)
                    sibling = node.parent.right

                if sibling.left.color == 'BLACK' and sibling.right.color == 'BLACK':
                    sibling.color = 'RED'
                    node = node.parent
                else:
                    if sibling.right.color == 'BLACK':
                        sibling.left.color = 'BLACK'
                        sibling.color = 'RED'
                        self._right_rotate(sibling)
                        sibling = node.parent.right

                    sibling.color = node.parent.color
                    node.parent.color = 'BLACK'
                    sibling.right.color = 'BLACK'
                    self._left_rotate(node.parent)
                    node = self.root
            else:
                sibling = node.parent.left
                if sibling.color == 'RED':
                    sibling.color = 'BLACK'
                    node.parent.color = 'RED'
                    self._right_rotate(node.parent)
                    sibling = node.parent.left

                if sibling.right.color == 'BLACK' and sibling.left.color == 'BLACK':
                    sibling.color = 'RED'
                    node = node.parent
                else:
                    if sibling.left.color == 'BLACK':
                        sibling.right.color = 'BLACK'
                        sibling.color = 'RED'
                        self._left_rotate(sibling)
                        sibling = node.parent.left

                    sibling.color = node.parent.color
                    node.parent.color = 'BLACK'
                    sibling.left.color = 'BLACK'
                    self._right_rotate(node.parent)
                    node = self.root

        node.color = 'BLACK'


    def _transplant_p(self, x, y):
        # 即使是叶节点也无所谓的
        y.parent = x.parent

        if x.parent is None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y



    # 左旋
    def _left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.nil:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def _right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.nil:
            y.right.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    def _find_node(self, key):
        current = self.root
        while current != self.nil and current.key != key:
            if key < current.key:
                current = current.left
            else:
                current = current.right
        return current
    #后序节点
    def _successor(self, node):
        if node.right != self.nil:
            return self._minimum(node.right)


    def _minimum(self, node):
        while node.left != self.nil:
            node = node.left
        return node
    # 中序遍历
    def inorder_traversal(self):
        result = []
        self._inorder_traversal(self.root, result)
        return result

    def _inorder_traversal(self, node, result):
        if node != self.nil:
            self._inorder_traversal(node.left, result)
            result.append(node.key)
            self._inorder_traversal(node.right, result)

    # 判断是否是二叉树
    def judge_balance(self):
        if self.root.color == 'RED':
            return False
        return not self._balance(self.root) == -1

    def _balance(self, node: Node):
        if node == self.nil:
            return 0
        if node.color == 'RED':
            if node.left.color == 'RED' or node.right.color == 'RED':
                return -1
        left, right = self._balance(node.left), self._balance(node.right)
        if left == right:
            if left == -1:
                return -1
            return left if node.color == 'RED' else 1+left
        return -1

    # 二叉树是否有序
    def judge_sort(self, arr):
        for i in range(1, len(arr)):
            if arr[i-1] > arr[i]:
                return False
        return True

    # 判断节点是否被删除
    def judge_delete(self, arr, key):
        l, r = 0, len(arr)
        while l < r:
            mid = (l+r)//2
            if arr[mid] == key:
                return False
            elif arr[mid] < key:
                l = mid + 1
            else:
                r = mid
        return True

if __name__ == "__main__":
    for _ in range(10):

        tree = RedBlackTree()
        for i in range(1000000):
            tree.insert(i)

        deletes = []
        for __ in range(5):
            delete_ = random.randint(0, 9999)
            tree.delete(delete_)
            deletes.append(delete_)
        inorders = tree.inorder_traversal()
        if not tree.judge_balance() and not tree.judge_sort(inorders):
            print(22222222222222222)
            break
        for a in deletes:
            if not tree.judge_delete(inorders, a):
                print(33333333333333333333)
                break
        print(_)